Date: Wed, 08 Jan 1997 20:36:24 GMT
Server: NCSA/1.4.2
Content-type: text/html

<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95 (Thu Jan 19 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE>CSE 322 
Assignment 10 
Due Friday, March 8, 1996</TITLE>
</HEAD>
<BODY>
<meta name="description" value="CSE 322 
Assignment 10 
Due Friday, March 8, 1996">
<meta name="keywords" value="hw10">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<P>
 <BR> <HR><A NAME=tex2html1 HREF="node1.html"><IMG ALIGN=BOTTOM ALT="next" SRC="http://www.cs.washington.edu/general/latex2html_icons//next_motif.gif"></A>   <IMG ALIGN=BOTTOM ALT="up" SRC="http://www.cs.washington.edu/general/latex2html_icons//up_motif_gr.gif">   <IMG ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.washington.edu/general/latex2html_icons//previous_motif_gr.gif">         <BR>
<B> Next:</B> <A NAME=tex2html2 HREF="node1.html">   About this document </A>
<BR> <HR> <P>
<P>
<H1>CSE 322 
Assignment 10 
Due Friday, March 8, 1996</H1>
<P><STRONG></STRONG><P>
<P><STRONG></STRONG><P>
<P>
<OL><LI>
Construct a DPDA which accepts the language <IMG  ALIGN=MIDDLE ALT="" SRC="img1.gif"> has an 
equal number of <b>a</b>'s and <b>b</b>'s<IMG  ALIGN=MIDDLE ALT="" SRC="img2.gif">.  Run your machine on the
input <b>abba</b>.
<LI> 
Use the construction given in class of a PDA from a context-free grammar
to construct a PDA which accepts the language generated by the
grammar <IMG  ALIGN=MIDDLE ALT="" SRC="img3.gif">.  Recall that
the language generated by this grammar is the language of number 1 above.
Run your machin on the input <b>abba</b>
<LI> 
Construct a one-tape Turing machine which accept the language
<IMG  ALIGN=MIDDLE ALT="" SRC="img4.gif">.  Please use the Turing machine
diagrams which are defined in Chapter 9.  Describe in English what
each of your states does, that is, describe the algorithm implemented
by your Turing machine.  Run your machine on the input <b>abcab</b>.
<LI>
Give a construction of the PDA from a context-free grammar where the
PDA behaves like the bottom-up parsing method.   You will need to ``shift''
input onto the stack and ``reduce'' according to the grammar productions.
Each reduction will have to broken up into a number of steps governed
by a set of states.  Try to make your construction as brief and elegant as the
top-down construction handed out.
</OL><BR> <HR>
<UL> 
<LI> <A NAME=tex2html3 HREF="node1.html#SECTION00010000000000000000">   About this document ... </A>
</UL>
<BR> <HR>
<P><ADDRESS>
<I>James Fix <BR>
Sun Mar  3 12:20:28 PST 1996</I>
</ADDRESS>
</BODY>
